int inv_mod(int x, int m) {
	int s = m, t = x; /* set up for gcd(x,m) */
	int a = 0, b = 1; /* 0*x = s and 1*x = t */
	int q, r, temp;

	while(t) {
		q = s/t;
		r = s%t; /* quotient and remainder */

		s = t;
		t = r; /* push back */

		temp = (a-b*q) % m;
		a = b;
		b = temp; /* push back */
	}

	if(s==1) {
		return (a>0)?a:(m+a);
	}
	else { // gcd(x,m) != 1
		return 0;
	}
}
